package NewCoder;

public class BM20 {
    public int InversePairs(int [] array) {
        return Inversenal(array,0,array.length-1);
    }
    public int Inversenal(int[] arr,int l,int r){
        if(l>=r) return 0;
        int mid=(r-l)/2+l;
        int leftNum=Inversenal(arr,l,mid);
        int rightNum=Inversenal(arr,mid+1,r);
        if(arr[mid]>arr[mid+1]){
            return (leftNum+rightNum+merge(arr,l,mid,r))%1000000007;
        }else{
            return (leftNum+rightNum)%1000000007;
        }
    }
    private int merge(int[] arr,int l,int mid,int r){
        int count=0;
        int[] temp=new int[r-l+1];
        for(int i=l;i<=r;i++){
            temp[i-l]=arr[i];
        }
        int i=l;
        int j=mid+1;
        for(int k=l;k<=r;k++){
            if(i>mid){
                arr[k]=temp[j-l];
                j++;
            }else if(j>r){
                arr[k]=temp[i-l];
                i++;
            }else if(temp[i-l]<=temp[j-l]){
                arr[k]=temp[i-l];
                i++;
            }else{
                arr[k]=temp[j-l];
                count=(count+(mid-i+1))%1000000007;
                j++;
            }
        }
        return count;
    }
}
